\documentclass[11pt,spanish]{article}
\usepackage[spanish,activeacute]{babel}
\usepackage[utf8]{inputenc}
\usepackage{graphicx}
\sloppy



\title{\includegraphics[scale=0.50]{logo}\\
		Universidad Nacional de Río Cuarto - FCEFQyN Departamento de Computación \\
		Simulación\\ 
			Proyecto: ''Sistema de Tiempo Compartido ” \\}
\author{Juan Pablo Demo \\
		Fernando Villar }
\begin{document}


\maketitle
\newpage
\section*{Sistema de Tiempo Compartido}
	Un Sistema de Tiempo Compartido (timesharing system) con 9 terminales se compone de una CPU y 2
discos de almacenamiento idénticos. Las cargas que provocan los usuarios de las terminales son similares
y siguen una distribución exponencial con una media de un comando cada 5 segundos.
El procesamiento de un comando generado desde una terminal (proceso) requiere un tiempo medio
de CPU de 480ms y un promedio de 4 requerimientos de acceso a disco.\\ El tiempo medio de intervalo
de uso de CPU entre 2 requerimientos a disco es de 120ms (480/4) y sigue una distribución exponencial.
Los requerimientos a disco estan distribuidos uniformemente entre los 2 discos.
El tiempo de servicio de un requerimiento de disco es la suma de los tiempos de búsqueda ( o posicionamiento), latencia y tiempo de transferencia.\\ Los tiempos mínimo y máximo de búsqueda 0 y 70ms,respectivamente. 
No se conoce la distribución de la media de búsqueda, pero observaciones permiten determinar
 que la mayoria de los tiempos de búsqueda están alrededor de 40ms (proponer una distribució
adecuada). Los tiempos de latencia están distribuidos uniformemente en [0, 26.7]ms. Los datos se transfieren
en en bloques, cada requerimiento transfiere un bloque y el tiempo de transferencia es de 52ms por
bloque. Las colas de espera de los discos siguen una politica FIFO.

\newpage
\tableofcontents
\newpage
\section{Estimación Analítica}
	\subsection{Tasas de Llegada}
		La tasa de llegada de comandos es de 1/5 seg , por terminal por lo tanto podemos determinar 
		\(\lambda{0}=1/5*9=9/5\). Luego podemos definir las restantes tasas de llegadas que figuran en la red de colas
		de la figura \ref{RD} \\
		\(\lambda{0}=9/5\)\\
		\(\lambda{1}=\lambda{0}+\lambda{4}+\lambda{5}\)\\
		\(\lambda{2}=\lambda{1}*0,4\)\\
		\(\lambda{3}=\lambda{1}*0,4\)\\
		\(\lambda{4}=\lambda{2}\)\\
		\(\lambda{5}=\lambda{3}\)\\
		\\donde 
		\begin{eqnarray}
			\lambda{1} & = & \lambda{0}+\lambda{4}+\lambda{5}\ = \nonumber \\
			\lambda{1} & = & 9/5 + (\lambda{1}*0,4) + (\lambda{1*0,4}) = \nonumber\\
		    \lambda{1}(1-0,4-0,4) & = & 9/5 = \nonumber\\
			\lambda{1} & = &  9 seg \nonumber\\
			\nonumber	
	\end{eqnarray}	
	\\por lo tanto \\
	\(\lambda{0}=9/5 seg\)\\
	\(\lambda{1}=9 seg\)\\
	\(\lambda{2}=3,6 seg\)\\
	\(\lambda{3}=3,6 seg\)\\
	\(\lambda{4}=3,6 seg\)\\
	\(\lambda{5}=3,6 seg\)\\
	\subsection{Medidas de performance cola CPU}
		\subsubsection{Utilización del servidor}
		En el análisis  del texto podemos observar que la cola correspondiente al servicio de CPU es 
		del tipo  M/M/1/\(\infty\)/\(\infty\).\\
		El tiempo de servicio de CPU posee una media de 480ms, además en promedio suceden cuatro accesos a disco, por lo tanto 			en promedio cada comando utiliza cinco ráfagas de CPU 480/5ms. Con esta información podemos calcular la tasa de 				servicio del CPU.\\
		\(\mu{1}=\frac{1}{480/5}ms=\frac{1}{0,480/5}seg=\frac{1}{0,096}seg = 10,416seg\)\\
		para el tipo de cola M/M/1/\(\infty\)/\(\infty\) la formula de calculo de utilización del servidor es la siguiente.\\
		\(\rho=\frac{\lambda{1}}{\mu{1}} = \frac{9}{10,416}=0,864\)	
		\subsubsection{Longitud promedio de la cola}
		Aplicando la formula para colas M/M/1/\(\infty\)/\(\infty\).\\
		\(L = \frac{\lambda{1}}{(\mu{1}-\lambda{1})}= \frac{9}{(10,416-9)} = \frac{9}{1,416} = 6,35\)  	
		\subsubsection{Tiempo medio de respuesta}
		Aplicando la formula para colas M/M/1/\(\infty\)/\(\infty\).\\
		\(w=\frac{1}{(\mu{1}-\lambda{1})}=\frac{1}{(10,416-9)}=\frac{1}{1,416}=0,70seg\)\\	
	\subsection{Medidas de performance cola DISCO}
		\subsubsection{Utilización del servidor}
		Se puede observar en la Figura \ref{RD}, que las dos colas que representan al servicio de disco son idénticas por lo 			tanto mostraremos los cálculos de una de ellas.\\
		El servicio de un disco esta constituido por tres etapas, búsqueda, latencia y transferencia. Del texto podemos 				determinar los siguientes datos.\\
		\begin{description}
			\item[•]Búsqueda - Distribución Triangular\\
			Valor mínimo = a = 0\\
			Máxima altura = b =40 \\
			Valor máximo = c = 70\\
			\(Media =\frac{a+b+c}{3} =\frac{(0+40+70)}{3}=\frac{110}{3}\)\\
			\(\sigma^2=\frac{(a^2+b^2+c^2+a*c-a*b-b*c)}{18}=205,55ms=2,05seg\)\\
			\item[•]Latencia - Distribución uniforme \\
			a=0\\
			b=26,7\\	
			\(Media=\frac{(a+b)}{2}=\frac{(0+26,7)}{2}=\frac{26,7}{2}=13,35\)\\
			\(\sigma^2=\frac{(b-a)^2}{12}=59,40ms=0,059seg\)\\
			\item[•]Transferencia-Constante\\
			\(tiempo=52ms=0,052seg\)\\	
		\end{description}
		Dado que el tiempo de servicio de DISCO es la suma de búsqueda, latencia y transferencia, cada una con una distribución 		estadística diferente,  tomamos la distribución de servicio como una distribución general por lo tanto obtenemos una 			cola del tipo  M/G/1/\(\infty\)/\(\infty\) donde.\\		
		\\\(E(x)=\frac{(110/3+13,35+52)}{3}=34ms=0.034s\)\\
 	    \(\sigma^2=2,05+0,059 = 2.109seg\)\\
		\\Por lo tanto la tasa de servicio.\\
		\(\mu{2}=\frac{1}{E(x)}=29,4seg\)\\
		\\En consecuencia la utilizacion del servidor para esta cola.\\
		\(\rho = \frac{\lambda{2}}{\mu{2}} = \frac{3,6}{29,4}=0,122\) 		
		\subsubsection{Longitud promedio de la cola}
		Aplicando la formula para colas M/G/1/\(\infty\)/\(\infty\).\\
		\(L=\rho + \frac{\rho^2*(1+\sigma^2*\mu{2}^2)}{2*(1-\rho)} = 14,66\)
		\subsubsection{Tiempo medio de respuesta}
		Aplicando la formula para colas M/G/1/\(\infty\)/\(\infty\).\\
		\(w=\frac{1}{\mu{2}}+\frac{\lambda{2}*(1/\mu{2}^2+\sigma^2)}{2*(1-\rho)}=4,36seg\)\\
\newpage
\section{Descripción gráfica de la red de colas utilizada }
	\begin{figure}[!hdp]
		\begin{center}
			\includegraphics[scale=0.40]{Diagrama2}
			\caption{Red de Colas Sistema de Tiempo compartido.\label{RD}}
		\end{center}
	\end{figure}
	
\section{Propuesta para la mejora de alguna de las medidas de performance}
	\begin{description}
		 \item[•]Agregar al sistema un cpu adicional de manera de mejorar el factor de utilización del CPU, además de   mejorar el tiempo medio de respuesta de los comandos y  la longitud de la cola de comandos.\\
		 
		 \item[•]Unificar las colas de los discos de requerimientos, para evitar que una de las colas de disco tenga sobre carga y la otra cola este vacía de manera que el disco de la misma este ocioso.\\
	\end{description}

\section{Implementación en OMNET++}
		Para el desarrollo de la simulación del  \textbf{ Sistema de Tiempo compartido} se utilizo la Herramienta OMNET++ 				(simulador modular de eventos discretos, orientado a objeto), en conjunto a la herramienta SVN(sistema de control de 			versiones) ubicado en el servidor provisto por google.
		El proyecto completo puede descargarse de\\
		\texttt{https://simulacion-demo-villar.googlecode.com/svn/trunk/ simulacion-demo-villar}\\
		 Para cada planificación existe una ejecución en particular que están dadas por los parámetros 	|								Network.cpu.priorityLess, Network.cpu.planHigher, Network.cpu.roundRobin. Definidos en el archivo omnetpp.ini.\\ 
		Cabe aclarar que no todas las ejecuciones posibles son validas.\\
		%\newpage
		 \begin{center}\textbf{Tabla de ejecuciones validas} \end{center}
		\begin{tabular}{|r ||r | r | r || c|}
			\hline
			NroEjecucion & priorityLess & planHigher & roundRobin & TipoSimulacion \\
			\hline
			\hline
			3 & 1 & 0 & 0 & priorityLess\\
			\hline
			5 & 0 & 1 & 0 & planHigher\\
			\hline
			6 & 0 & 0 & 1 & roundRobin\\
			\hline
			7 & 0 & 0 & 0 & FIFO\\
			\hline
		\end{tabular}
		\\			
		\\Para cada numero de ejecución se genera un archivo de salida con los diferentes estadísticos,
	   	ubicados en el directorio \textbf{result}.\\ 
	   	Además para la terminación de la simulación Utilizamos una librería que implementa un algoritmo, en la clase 				cADByStddev ( hereda de cAccuracyDetection), que divide la desviación estándar por el cuadrado del número de 				muestras recogidas y comprueba si el valor obtenido es lo suficientemente pequeño para determinar una cierta 				precisión en los resultados. El método setParameters permite ajustar los parámetros del algoritmo como la 					precisión o el número de repeticiones que queremos ejecutar para obtener el resultado,el método collect  permite 			la recolección de datos y el método detected permite terminar la simulación cuando se determina la precisión 				adecuada.\\
		para la comparación de  las planificaciones, la ejecución de cada simulación se realizo con un tiempo constante 			para asegurar que la diferencia de los estadísticos no esta ligado al tiempo de simulación, aunque comprobaciones posteriores aseguraron que esto no es un problema cuando la simulación es estable.\\
		A continuación se muestran los resultados de la simulación para las diferentes planificaciones de CPU.\\	
	\subsection{planificación FIFO}
	El  numero  correspondiente a la planificación es 7 , por lo tanto podemos observar los estadísticos en el archivo 				\textbf{General-7.sca} ubicado 	en el directorio \textbf{result}.\\  
	\begin{center} 
	 \textsl{  scalar Network.cpu 	"simulated time" 90000.02720152\\
		scalar Network.cpu 	"Cpu Used" 	0.86324979145594\\
		scalar Network.cpu 	"Queue Size" 	8.7050081541124\\
		  scalar Network.cpu 	"Response Time" 	5.7032192340495\\}
	\end{center}
	Podemos comparar los resultados con los analíticos, y vemos que los valores de factor utilización de procesador  son muy cercanos, así también como el tiempo que un comando pasa en el sistema ya que si sumamos los valores analíticos del tiempo que pasa en disco mas tiempo que pasa en CPU 4,36 + 0,70 = 5,06.
 Lo que varia es la longitud promedio de la cola en 2 unidades, esto puede deberse al tiempo de la simulación ya que los valores analíticos son valores a muy largo plazo.\\
No compararemos los valores analíticos de la cola disco , con la simulación ya que  difieren debido a que tomamos una distribución de servicio general.De todas maneras en cada ejecución de la simulación se muestra el factor de utilización de disco y el tamaño promedio de la cola de disco.\\
	\subsection{planificación ROUND ROBIN}
		El  numero  correspondiente a la planificación es 6 , por lo tanto podemos observar los estadísticos en el archivo 				\textbf{General-6.sca} ubicado 	en el directorio \textbf{result}.\\  
	\begin{center} 
	
	 \textsl{scalar Network.cpu 	"simulated time" 	90000.00711677\\
		scalar Network.cpu 	"Cpu Used" 	0.86241342886231\\
		scalar Network.cpu 	"Queue Size" 	1.207203048492\\
		scalar Network.cpu 	"Response Time" 	1.1183191697146\\  }
	\end{center}
	Los resultados fueron obtenidos con un quantum de 0.09. \\
	\subsection{planificación PRIORIDAD MAS CORTO}	
		El  numero  correspondiente a la planificación es 3 , por lo tanto podemos observar los estadísticos en el archivo 				\textbf{General-3.sca} ubicado 	en el directorio \textbf{result}.\\  
	\begin{center} 
	
	 \textsl{scalar Network.cpu 	"simulated time" 	90000.065111785\\
		scalar Network.cpu 	"Cpu Used" 	0.86610108113329\\
		scalar Network.cpu 	"Queue Size" 	3.5052035167241\\
		scalar Network.cpu 	"Response Time" 	2.8065508100978\\ }
	\end{center}	
	\subsection{planificación TASA DE RESPUESTA MAS ALTA}
	El  numero  correspondiente a la planificación es 5 , por lo tanto podemos observar los estadísticos en el archivo 				\textbf{General-5.sca} ubicado 	en el directorio \textbf{result}.\\  
	\begin{center} 
	
	 \textsl{scalar Network.cpu 	"simulated time" 	90001.204641376\\
			scalar Network.cpu 	"Cpu Used" 	0.85919017640707\\
			scalar Network.cpu 	"Queue Size" 	4.856712442303\\
			scalar Network.cpu 	"Response Time" 	3.5474380847604\\
			 }
	\end{center}	
	
	\subsection{Comparación entre las diferentes planificaciones de CPU}
		Para la comparación de las diferentes planificaciones hicimos uso de los elementos que nos provee la herramienta 				utilizada para la simulación OMNET++. \\
		Realizando la creación de archivos escalares  a la finalización  de la simulación donde se guardan los estadísticos de 			interés por cada ejecución. Permitiendo la generación de gráficas mediante la misma herramienta.\\

		\subsubsection*{Factor de utilización del procesador}
			\begin{center}\textbf{Tabla de  Comparacion de utilización del servidor} \end{center}
			\begin{tabular}{|r |r | r | r | }
				\hline
				FiFO & RoundRobin & planHigher & priorityLess   \\
				\hline
				\hline
				  0.86324979145594 & 0.86241342886231 & 0.85919017640707 & 0.86610108113329 \\
				\hline
			\end{tabular}\\
			\\En la tabla se puede observar una paridad  evidente en cuanto al factor de utilización del CPU entre las 						diferentes planificaciones\\ 
			A continuación se muestran las gráficas comparativas.\\
			\newpage	
			\begin{center}\textbf{Tabla de identificación  de planificación} 
			\begin{tabular}{|c | c | c | c |}
				\hline
				FiFO & RoundRobin & planHigher & priorityLess   \\
				\hline
				\hline
				  azul & rojo & verde & amarillo \\
				\hline
			\end{tabular}
			
			\end{center}	
			\begin{figure}[!hdp]
				\begin{center}
					\includegraphics[scale=0.40]{GeneralCpu}
					\caption{Grafico de Barras de factor de utilizacion del servidor \label{BS}}
				\end{center}
			\end{figure}	
			Observando el gráfico de barras con mas detalles podemos observar que la planificación de Tasa de respuesta 				mas alta posee el factor de utilización  del CPU mas bajo por lo contrario la planificación de prioridad mas 				corto tiene el mayor tasa.\\	
			%\newpage
			\begin{figure}[!hdp]
				\begin{center}
					\includegraphics[scale=0.40]{GeneralCpu1}
					\caption{Grafico de Barras de factor de utilizacion del servidor \label{BS1}}
				\end{center}
			\end{figure}	
			
					
		\newpage	
		\subsubsection*{Longitud Promedio de la Cola}
			
			\begin{center}\textbf{Tabla de  Comparacion de Longitud Promedio de la Cola} \end{center}
			\begin{tabular}{|r |r | r | r | }
				\hline
				FiFO & RoundRobin & planHigher & priorityLess   \\
				\hline
				\hline
					8.705008154112 & 1.207203048492 & 4.856712442303 & 3.5052035167241 \\
				\hline
			\end{tabular}\\			
			\begin{center}\textbf{Tabla de identificación  de planificación} 
			\begin{tabular}{|c | c | c | c |}
				\hline
				FiFO & RoundRobin & planHigher & priorityLess   \\
				\hline
				\hline
				  azul & rojo & verde & amarillo \\
				\hline
			\end{tabular}
			\end{center}
			%\newpage
			\begin{figure}[!hdp]
				\begin{center}
					\includegraphics[scale=0.40]{GeneralTamanoCola}
					\caption{Grafico de barras de Longitud Promedio de la Cola\label{BC}}
				\end{center}
			\end{figure}
		Podemos observar que la planificación Round  Robin  obtiene menor longitud promedio de cola, seguido por las 					planificación prioridad mas corto y planificación de la tasa de respuesta mas alta.\\	
		
		\subsubsection*{Tiempo medio de un Comando en el sistema}
			\begin{center}\textbf{Tabla de  Comparacion de Tiempo medio de un Comando en el Sistema} \end{center}
			\begin{tabular}{|r |r | r | r | }
				\hline
				FiFO & RoundRobin & planHigher & priorityLess   \\
				\hline
				\hline
				  5.7032192340495 & 1.1183191697146 & 3.5474380847604 & 2.8065508100978 \\
				\hline
			\end{tabular}\\
			\begin{center}\textbf{Tabla de identificación  de planificación} 
			\begin{tabular}{|c | c | c | c |}
				\hline
				FiFO & RoundRobin & planHigher & priorityLess   \\
				\hline
				\hline
				  azul & rojo & verde & amarillo \\
				\hline
			\end{tabular}
			\end{center}
			%\newpage
			\begin{figure}[!hdp]
				\begin{center}
					\includegraphics[scale=0.40]{GeneralTiempoRespuesta}
					\caption{Grafico de Barra de Tiempo Medio de Respuesta del Sistema\label{BTR}}
				\end{center}
			\end{figure}	
			Podemos observar que en la planificación Round  Robin  un comando pasa menos tiempo en el sistema, seguido por las 			planificación prioridad mas corto y planificación de la tasa de respuesta mas alta.\\
		En conclusión podemos decir que los mejores resultados fueron obtenidos por la planificación Round Robin, y a nuestro 			criterio la segunda planificación candidata es la planificación de tasa de respuesta mas alta, no obtiene mejores 				resultados que la planificación por prioridad mas corto, pero asegura que se atienden todos los comandos, con mejor 			performance que la planificación FIFO.\\
Cabe aclarar que NO se tiene en cuenta el tiempo que le requiere al CPU cambiar de comando, por lo que la planificación  Round Robin se beneficia con tiempos muy bajos de quantum.\\   		 
\end{document}	
	